# ДЗ

Требуется реализовать методы сортировки Sort() всех классах `BubbleSort.cs`, `InsertionSort.cs`, `SelectionSort.cs`, `MergeSort.cs`, `QuickSort.cs` файлы находятся в папке Algorithms и проверить их соответсвующими тестами.

*Запуск тестов:* 
**Visual Studio**
Откройте обозреватель тестов, выбрав Тест > Обозреватель тестов в верхней строке меню (или нажмите клавиши CTRL + E, T).
Запустите модульные тесты, нажав Запустить все (или нажмите клавиши CTRL + R, V).

Все методы которые мы будем писать используют объект массив объектов `Item`, это позволяет подсчитать количество сравнений произведенных при сортировке и таким образом сравнить алгоритмы сортировки между собой.

 - Для сравнения используйте метод Item `int CompareTo(Object object)` - если элементы равны будет возврат 0, если тот объект у кого вызвали больше того что передали в аргумент то вернется -1, в обратном случае 1.

```C#
Item big = new Item(100);
Item little = new Item(1);

Console.WriteLine(big.CompareTo(little)); // 1
```

 - В результате проверки сортировки у вас будет следующий вывод при провале теста:

```
expected:   [1, 2, 3]
actual:     [3, 2, 1]
```
значения для отображения элементов массива используют значение `int data` класса `Item`.

## 1. Сортировка пузырьком

★★☆☆☆

Такой способ считается самым простым в понимании и реализации. Проверяем каждый элемент и выталкиваем его вверх, если элемент больше своего соседа.

Напишите реализацию в классе `BubbleSort.cs`

```C#
Sort(Item[] items)
```

Запуск тестов в классе BubbleSortTest.cs


## 2. Сортировка вставками

★★☆☆☆

Данный метод просматривает каждый элемент по одному, и передвигает элемент на нужное место в левой части массива, который всегда уже отсортирован.

Напишите реализацию в классе `InsertionSort.cs`

```C#
Sort(Item[] items)
```

Запуск тестов в классе InsertionSortTest.cs

## 3. Сортировка выбором

★★★☆☆

Ищем каждый раз минимальный элемент и вставляем его в начало отсортированного фрагмента. Повторяем до обхода всех элементов.

Напишите реализацию в классе `SelectionSort.cs`

```C#
Sort(Item[] items)
```

Запуск тестов в классе SelectionSortTest.cs

## 4. Сортировка слиянием

★★★★☆

Разбираем массив элементов на группы, сортируем каждую группу отдельно, и слиянием собираем массива обратно.

Напишите реализацию в классе `MergeSort.cs`

```C#
Sort(Item[] items)
```

Запуск тестов в классе MergeSortTest.cs

## 5. Быстрая сортировка

★★★★★

Универсальный и один из самых быстрых известных алгоритмов сортировки.
Выбираем опорный элемент в массиве, размещаем отстальные элементы справа от опорного - больше чем опорный,
слева от опорного - меньше чем опорный. В каждом из получившемся наборе элементов массива повторяем это действие - выбор опорного элемента, расположение элементов по обе стороны от него.

Напишите реализацию в классе `QuickSort.cs`

```C#
Sort(Item[] items)
```

Запуск тестов:

Запуск тестов в классе QuickSortTest.cs

## 💡 Рекомендации

Для наглядного представления как работают сортировки [посмотрите визуализации различных выдов сортировок](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html)

нажмите `Randomize Array` для получения несортированного массива и далее кнопками c названиями методов сортировки запустите и наблюдайте.